package slidingwindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by fengliejv on 2017/10/1.
 */
public class RepeatedDNASequences187 {

    //使用滑动窗口 + map + bit calculate
    public List<String> findRepeatedDnaSequences(String s) {
        Map<Character, Integer> dict = new HashMap<>();
        dict.put('A', 0);
        dict.put('C', 1);
        dict.put('G', 2);
        dict.put('T', 3);

        if (s.length() < 10) {
            return new ArrayList<>();
        }

        List<String> result = new ArrayList<String>();
        HashMap<Integer, Integer> map = new HashMap();
        int digit = 0;
        for (int i = 0; i < 10; i++) {
            digit = (digit << 2) | dict.get(s.charAt(i));
        }
        map.put(digit, 1);
        for (int i = 10; i < s.length(); i++) {
            int input = dict.get(s.charAt(i));
//            int output = dict.get(s.charAt(i));
            //去除19、20位
            digit = digit & ((1 << 18) - 1);
            //补充1、2位
            digit = (digit << 2) | input;
            Integer count = map.getOrDefault(digit, 0);
            count++;
            if (count == 2) {
                result.add(s.substring(i - 9, i+1));
            }
            map.put(digit, count);
        }
        return result;
    }

    //使用map
    public List<String> findRepeatedDnaSequences2(String s) {
        List<String> list = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap();
        for (int i = 0; i < s.length() - 9; i++) {
            String sub = s.substring(i, i + 10);
            if (map.containsKey(sub)) {
                int val = map.get(sub);
                if (val == 1) {
                    map.put(sub, 2);
                    list.add(sub);
                }
            } else {
                map.put(sub, 1);
            }
        }
        return list;
    }
}
